//
// Created by ASUS on 2024/1/29.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5;

//做一维前缀和成为原数组，下标从0开始
void diff(int l,int r,int v){
	int n;
	vector<int> d(n+1);
	d[l]+=v;
	d[r+1]-=v;
	//复原数组
	{
		vector<int> arr(n);
		arr[0]=d[0];
		for(int i=1;i<n;i++) arr[i]=d[i]+=arr[i-1];
	}
}
//做二维前缀和成为原矩阵，下标从0开始
void diff2D(int x1,int y1,int x2,int y2,int v){
	int m;int n;
	vector<vector<int>> d(m+1,vector<int> (n+1));
	d[x1][y1]+=v;
	d[x2+1][y1]-=v;
	d[x1][y2+1]-=v;
	d[x2+1][y2+1]+=v;
	vector<vector<int>>  arr(m,vector<int>(n));
	//复原矩阵
	{
		arr[0][0] = d[0][0];
		for (int i = 1; i < m; ++i) {
			arr[i][0] = d[i][0] +=  arr[i - 1][0];
		}
		for(int i=1;i<n;i++){
			arr[0][i] = d[0][i] +=  arr[0][i - 1];
		}

		for (int i = 1; i < m; ++i) {
			for (int j = 1; j < n; ++j) {
				arr[i][j] = d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
			}
		}
	}
}


int main(){


}